package org.example.day01;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO
 * 假定街道是棋盘型的，每格距离相等，车辆通过每格街道需要时间均为 timePerRoad；
 * 街道的街口（交叉点）有交通灯，灯的周期T(=lights[row][col])各不相同；
 * 车辆可直行、左转和右转，其中直行和左转需要等相应T时间的交通灯才可通行，右转无需等待。
 * 现给出 n*m 个街口的交通灯周期，以及起止街口的坐标，计算车辆经过两个街口的最短时间。
 * 其中：
 * 1）起点和终点的交通灯不计入时间，且可以任意方向经过街口
 * 2）不可超出 n*m 个街口，不可跳跃，但边线也是道路（即 lights[0][0] -> lights[0][1] 是有效路径）
 *
 * 入口函数定义:
 * lights : n*m 个街口每个交通灯的周期，值范围[0,120]，n和m的范围为[1,9]
 * timePerRoad : 相邻两个街口之间街道的通过时间,范围为[0,600]
 * rowStart : 起点的行号 * colStart : 起点的列号
 * rowEnd : 终点的行号 * colEnd : 终点的列号
 * return : lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间
 * int calcTime(int[][] lights,int timePerRoad,int rowStart,int colStart,int rowEnd,int colEnd)
 * @date 2024/3/11 15:22
 */
public class test020 {
    // 定义每个街口的四个方向（上，右，下，左）
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {
        // 创建一个n*m的二维数组来记录每个街口到起点的最短时间
        int n = lights.length;
        int m = lights[0].length;
        int[][] minTime = new int[n][m];

        // 初始化起点的时间为0
        minTime[rowStart][colStart] = 0;

        // 创建一个队列来保存待处理的街口
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{rowStart, colStart});

        // BFS遍历直到队列为空
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentRow = current[0];
            int currentCol = current[1];
            int currentTime = minTime[currentRow][currentCol];

            // 遍历四个方向
            for (int[] direction : DIRECTIONS) {
                int newRow = currentRow + direction[0];
                int newCol = currentCol + direction[1];

                // 检查新坐标是否在棋盘范围内
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {
                    // 计算到达新街口的时间
                    int newTime = currentTime + timePerRoad;

                    // 如果是直行或左转，需要加上交通灯时间
                    if (direction[0] != 0 || direction[1] != 0) {
                        newTime += lights[newRow][newCol];
                    }

                    // 如果到达新街口的时间比之前记录的更短，则更新记录并加入队列
                    if (newTime < minTime[newRow][newCol]) {
                        minTime[newRow][newCol] = newTime;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
        }

        // 返回终点的最短时间
        return minTime[rowEnd][colEnd];
    }

    public static void main(String[] args) {
        // 测试数据
        int[][] lights = {
                {0, 0, 0},
                {0, 0, 0},
                {0, 0, 0}
        };
        int timePerRoad = 1;
        int rowStart = 0, colStart = 0;
        int rowEnd = 2, colEnd = 2;

        // 计算最短时间
        int shortestTime = calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd);
        System.out.println("The shortest time is: " + shortestTime);
    }
}
